class Solution {
    /*
        取模优化代码
    */      
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Deque<Integer> st = new LinkedList<>();
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for(int i=0; i<n*2; i++){
            while( !st.isEmpty() && nums[ st.peek()%n ]<nums[i%n] ){
                ans[ st.pop()%n ] = nums[i%n];
            }
            st.push(i);
        }
        return ans;
    }
}

class Solution {
    /*
        我的垃圾代码
    */  
    public int[] nextGreaterElements(int[] nums) {
        Deque<Integer> st = new LinkedList<>();
        int[] nums2 = new int[nums.length*2];
        int[] ans = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            ans[i] = -1;
            nums2[i] = nums2[i+nums.length] = nums[i];
        }
        for(int i=0; i<nums2.length; i++){
            while( !st.isEmpty() && nums2[ st.peek() ]<nums2[i] ){
                if( st.peek()<nums2.length/2 ){
                    ans[ st.peek() ] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }
}